package com.tgy.binarysearch.sort;

import java.util.Objects;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 2020-11-17 15:37
 */
public class Sort {

    public static void quickSort(Integer[] nums) {


        if (Objects.isNull(nums) || nums.length <= 1) {

            return;
        }

//        subQuickSort(nums,0,nums.length);
        nonRecursiveQuickSort(nums);
    }

    /**
     * 非递归
     * @param nums
     */
    private static void nonRecursiveQuickSort(Integer[] nums) {

        Stack<Integer> stack = new Stack<>();

        stack.push(nums.length);
        stack.push(0);
        int start, end;
        while (!stack.isEmpty()) {

            start = stack.pop();
            end = stack.pop();

            int left = start, right = end - 1;

            int base = nums[left];

            while (left < right) {

                while (left < right && nums[right] > base) {

                    right--;
                }

                if (left < right) {

                    nums[left++] = nums[right];
                }

                while (left < right && nums[left] < base) {

                    left++;
                }

                if (left < right) {

                    nums[right--] = nums[left];
                }
            }

            nums[left] = base;

            if (left - start > 1) {

                stack.push(left);
                stack.push(start);
            }

            if (end - left > 2) {

                stack.push(end);
                stack.push(left+ 1);
            }
        }


    }

    /**
     * 排序范围 [start,end) ,元素个数 end - start
     * @param nums
     * @param start
     * @param end
     */
    private static void subQuickSort(Integer[] nums,int start, int end) {

        if (end - start <= 1) {

            return;
        }

        Integer base = nums[start];
        int left = start, right = end - 1;
        while (left < right) {

            while (left < right && nums[right] > base) {

                right--;
            }

            if (left < right) {

                nums[left++] = nums[right];
            }

            while (left < right && nums[left] < base) {

                left++;
            }

            if (left < right) {

                nums[right--] = nums[left];
            }
        }

        nums[left] = base;

        subQuickSort(nums,start,left);
        subQuickSort(nums,left + 1, end);
    }
}
